import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestDemo7 {
    //给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
    //第一种方法
    public boolean isAnagram1(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] as = s.toCharArray();
        char[]at=t.toCharArray();
        int []map=new int[26];
        int count=0;//用来计数
        for(int i=0;i<as.length;i++) {
            if (++map[as[i]-'a'] == 1) {//代表出现过一次
                count++;
            }if(--map[at[i]-'a']==0){//上次出现过然后再减
                count--;
            }
        }return count==0;//为0表示为真
        }
        //第二种方法
    public boolean isAnagram2(String s,String t){
        if(s.length()!=t.length()){
            return false;
        }int[]count=new int [26];
        for(int i=0;i<s.length();i++){//charAt是取字符串转化为数组下标的值
            count[s.charAt(i)-'a']++;
        }for(int j=0;j<t.length();j++){
            count[t.charAt(j)-'a']--;
        }for(int c:count){
            if(c!=0){
                return false;
            }
        }return true;
    }

    //给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
    public int firstUniqChar(String s) {
        int []count=new int[26];
        char[]array=s.toCharArray();
        for(int i=0;i<array.length;i++){
            count[array[i]-'a']++;//这个-a的意思是array[i]字符的ASII的值减去a的ASII的值
        }for(int j=0;j<array.length;j++){
            if(count[array[j]-'a']==1){
                return j;
            }
        }return -1;
    }

    public int reverse(int x) {
        long ret=0;
        if(x==0){
            return 0;
        }
        while (x != 0) {
            ret=ret*10+x/10;
            x=x/10;
        }return (int)ret==ret?(int)ret:0;
    }
    public ListNode partition(ListNode head,int x){
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;
        while(cur!=null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                    cur = cur.next;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    as.next = cur;
                    ae = ae.next;
                    cur = cur.next;
                }
            }
        }if(bs==null){
            return as;
        }as=be.next;
        if(as!=null){
            ae.next=null;
        }return bs;
    }
    //在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
public ListNode deleteDuplication(ListNode head){
   ListNode cur=head;
   ListNode newHead=new ListNode(-1);
   ListNode tem=newHead;
   while(cur!=null){
       if(cur.next!=null&&cur.val==cur.next.val){
           while(cur.next!=null&&cur.val==cur.next.val){
               cur=cur.next;
           }cur=cur.next;
       }else{
          tem.next=cur;
          tem=tem.next;
          cur=cur.next;
       }
   }tem.next=null;
   return newHead;
}
    public int[]intersect(int []nums1,int []nums2){
        List<Integer> list=new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
       int i=0;
       int j=0;
       while(i< nums1.length&&j< nums2.length){
           if(nums1[i]<nums2[j]){
               i++;
           }else if(nums1[i]>nums2[j]){
               j++;
           }else{
               list.add(nums1[i]);
               i++;
               j++;
           }
        }int []tem=new int [list.size()];
       for(int m=0;m<tem.length;m++){
           tem[m]=list.get(m);
       }return tem;
    }
    public int []plusOne(int []digits){
        for(int i=digits.length-1;i>=0;i--){
            if(digits[i]!=9){
                digits[i]++;
                return digits;
            }else{
                digits[i]=0;
            }
        }int[]array=new int[digits.length+1];
        array[0]=1;
        return array;
    }
    //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    public void moveZero(int []nums){
        int i=0;
        int j=0;
       for(j=0;j<nums.length;j++){
           if(nums[j]!= 0){
               int tem=nums[i];
               nums[i]=nums[j];
               nums[j]=tem;
               i++;
           }
        }
    }
    //给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    public int []twoSum(int []nums,int target){
        int i=0;
        int j=1;
        int tem=nums.length-1;
        while(nums[i]+nums[j]!=target){
            if(tem==j){
                i++;
                j=i;
            }j++;
        }if(nums[i]+nums[j]==target){
            return new int[]{i,j};
        }return new int []{-1,-1};
    }
}
